struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


//在搜索二叉树中插入节点，只需按大小比较然后移动直到遇到空节点即可
//空节点就是新节点的位置

//递归法
TreeNode* insertIntoBST_(TreeNode* root, int val) {


    //终止条件
    if(!root){
        root=new TreeNode(val);
        return root;
    }

    //找路
    if(root->val<val) root->right=insertIntoBST_(root->right,val);
    if(root->val>val) root->left=insertIntoBST_(root->left,val);

    return root;
}







//迭代法
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if(!root) {root=new TreeNode(val); return root;}
    TreeNode* cur=root;
    TreeNode* pre;  //一定要用一个pre来存储上一个节点
    bool left=0;     //记录上一次移动是左还是右
    while(cur){
        if(cur->val>val) {cur=cur->left;left=1;}
        else if(cur->val<val) {cur=cur->right;left=0;}
        if(cur) pre=cur;
    }
    cur=new TreeNode(val);  //new以后还要指定位置
    
    
    if(left) pre->left=cur;
    else pre->right=cur;
    
    /*
    if(pre->val>val) pre->left=cur;
    else pre->right=cur;
    return root;
   */                       // 也可以这样判断
}